package leetcode_200;


import java.util.LinkedList;
import java.util.Queue;

/**
 *@author 周杨
 *NumberOfIslands_200 孤岛问题 
 *describe:用深度优先遍历 AC 20% 非递归 递归 100%
 *2018年6月11日 上午10:53:00
 */
public class NumberOfIslands_200 {
	Queue<Integer> x=new LinkedList<Integer>();
	Queue<Integer> y=new LinkedList<Integer>();
	char [][] grid;
	public static void main(String[] args) {
		NumberOfIslands_200 test=new NumberOfIslands_200();
		char grid[][]=new char[][] {{'1','1','1'},{'0','1','0'},{'1','1','1'}};
		System.out.println(test.numIslands(grid));

	}
	
	public int numIslands(char[][] grid) {
		this.grid=grid;
		int res=0;
        for(int i=0;i<grid.length;++i) {
        	for(int j=0;j<grid[0].length;++j) {
        			if(grid[i][j]=='1') {
        				res++;
        				fill(i,j);
        			}
        		}
        	}
        return res;
    }
	
	public void fill(int x,int y) {
		this.x.add(x);
		this.y.add(y);
		while(this.x.size()>0) {
			int x1=this.x.poll();
			int y1=this.y.poll();
			if(x1-1>=0&&grid[x1-1][y1]=='1') {
				this.x.add(x1-1);
				this.y.add(y1);
				grid[x1-1][y1]='2';
			}
			if(y1-1>=0&&grid[x1][y1-1]=='1') {
				this.x.add(x1);
				this.y.add(y1-1);
				grid[x1][y1-1]='2';
			}
			if(x1+1<grid.length&&grid[x1+1][y1]=='1') {
				this.x.add(x1+1);
				this.y.add(y1);
				grid[x1+1][y1]='2';
			}
			if(y1+1<grid[0].length&&grid[x1][y1+1]=='1') {
				this.x.add(x1);
				this.y.add(y1+1);
				grid[x1][y1+1]='2';
			}
		}
	}

	
	public int numIslands1(char[][] grid) 
    {
        if(grid == null || grid.length == 0)
            return 0;
        int l = grid.length;
        int w = grid[0].length;
        int count = 0;
        for(int i=0; i<l; i++)
        {
            for(int j=0; j<w; j++)
            {
                if(grid[i][j] == '1')
                {
                    dfsExplore(grid, i, j);
                     count++;
                }
               
            }
        }
        return count;
    }
    
    private void dfsExplore(char[][] grid, int i, int j)
    {
        if(i<0 || j<0 || i>grid.length-1 || j > grid[0].length-1 || grid[i][j] != '1')
        {
            return;
        }
        grid[i][j] = '0';
        dfsExplore(grid, i+1, j);
        dfsExplore(grid, i-1, j);
        dfsExplore(grid, i, j+1);
        dfsExplore(grid, i, j-1);
    }
}
